LOJ 6031「雅礼集训 2017 Day1」字符串

题目描述

令 $ s$ 与 $w$ 为两字符串，定义：

1. $w[l,r]$ 表示字符串 $w$ 在区间$[l,r]$ 中的子串；
2. $w $ 在 $s$ 中出现的频率定义为$w$ 在$s$ 中出现的次数；
3. $f(s,w,l,r)$表示 $w[l,r]$在$s$中出现的频率。

比如$ f(ababa,aba,1,3)=2$。

现在给定串 $s$，$m$个区间$[l,r]$ 和长度 $k$，你要回答 $q$个询问，每个询问给你一个长度为 $k$ 的字符串 $w$和两个整数 $a,b $,求：

$$\sum_{i=1}^bf(s,w,l_i,r_i)$$

输入格式

第一行四个整数 $n,m,q,k$, $n$ 表示 $ s $ 的长度。
接下来一行一个长为$ n $ 的字符串$ s $。
接下来$ m $行，每行两个整数表示 $l_i, r_i$。
接下来$ q $行，每行一个字符串 $w$ ，两个整数 $a,b$ 。

输出格式

对于每个询问一行，输出答案。

样例

样例输入

8 5 3 3
abacdaba
0 2
1 2
0 0
2 2
1 2
dab 1 4
bac 2 3
eeb 1 3

样例输出

7
3
2

数据范围与提示

对于$ 10\% $的数据，$n,m,k,q≤10$ ；
对于$ 30\% $ 的数据，满足 $n,m,k,q≤10^2$；
对于$ 50\%$ 的数据，满足 $n,m,k,q≤10^4$；
对于$100\% $的数据，满足 $n, m, k, q \leq 10 ^ 5, \sum w \leq 10 ^ 5$，字符串由小写英文字母构成。

---

询问一个串在另一个串中的出现次数，显然考虑后缀自动机。

设$S=\sum w\leq10^5$。这个条件提示我们考虑时间复杂度时应该重视所有询问串的长度总和，按照之前的套路应该就是把这些询问串全部拼在一起之类的，然而这道题并不行……

正解是，由于$kq=S \leq 10^5$考虑设置阈值，针对不同数据范围设计不同算法。

大体上有两种情况：单个询问串长度很短，但询问串个数很多；单个询问串长度很长，但询问串个数很短。

询问串个数很多但长度很小时，可以对每个串用$O(k^2)$的时间复杂度处理出每个区间在$s$中的出现次数。具体来讲就是枚举区间起点，在区间终点指针移动的同时在自动机上转移状态。之后采用二分查找或者是莫队算法得出每个询问串的答案。

二分查找的时间复杂度是$O(qk^2logm=Sklogm)$的。对于$k$较小的数据可以胜任，然而当$k$较大的时候就不行了。

当$k$很大时，询问串个数很少，那么$qm$就不会很大，就可以对于每一个串依次处理每一个询问区间。怎样快速得到某个串的子串在另一个串中的出现次数呢？利用字符串经典的“子串=后缀的前缀”的思想，用$O(k)$的时间复杂度处理出询问串的每一个前缀在自动机上匹配到的状态和长度，倍增找到后缀自动机上对应的节点即可。

这样做的时间复杂度是$O(q(k+mlogm)=S+qmlogm)$的，可以看到当$q$较小的时候可以胜任，而$q$较大时就不行了。

综上所述，只需要对$k$设置一个阈值，根据数据范围选择使用哪一种算法即可。

所以这是一道暴躁的二合一题目，然而由于SAM的优越性，代码并不如某些数据结构长。

---

写完之后发现namespace是没必要的，懒得改了……

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
#define MAXN 400005
#define Y 333
using namespace std;

int N,M,Q,K,L[MAXN],R[MAXN];
ll Ans=0;
char s[MAXN],w[MAXN];

namespace SAM{
	int tot,rt,las,par[MAXN][20],mx[MAXN],son[MAXN][26],sz[MAXN];
	bool vis[MAXN];
	vector<int>G[MAXN];

	int push(int val){mx[++tot]=val;return tot;}
	void init(){tot=0;las=rt=push(0);}

	void ins(int t){
		int p,q,np,nq;
		np=push(mx[las]+1);sz[np]=1;
		for(p=las;p&&(!son[p][t]);p=par[p][0])son[p][t]=np;
		if(!p)par[np][0]=rt;
		else{
			q=son[p][t];
			if(mx[q]==mx[p]+1)par[np][0]=q;
			else{
				nq=push(mx[p]+1);
				memcpy(son[nq],son[q],sizeof(son[q]));
				par[nq][0]=par[q][0];
				par[q][0]=par[np][0]=nq;
				for(;p&&son[p][t]==q;p=par[p][0])son[p][t]=nq;
			}
		}
		las=np;
	}

	void build(){for(int i=2;i<=tot;i++)G[par[i][0]].push_back(i);}

	void dfs(int x){
		for(int i=1;i<20;i++)par[x][i]=par[par[x][i-1]][i-1];
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i];dfs(y);
			sz[x]+=sz[y];
		}
	}

	void match(int &p,int t,int &len){
		while(p&&(!son[p][t]))p=par[p][0],len=mx[p];
		if(p)p=son[p][t],len++;
		else p=rt,len=0;
	}

	int jump(int p,int l){
		for(int i=19;i>=0;i--)if(mx[par[p][i]]>=l)p=par[p][i];
		return p;
	}
}

void solve1(){
	vector<int>q[Y][Y];
	int i,j,a,b,p,l,r,cnt=0;
	for(i=0;i<M;i++)q[L[i]][R[i]].push_back(i);
	while(Q--){
		scanf("%s%d%d",w,&a,&b);
		Ans=0;
		for(i=0;i<K;i++){
			p=SAM::rt;
			for(j=i;j<K;j++){
				p=SAM::son[p][w[j]-'a'];
				if(p==0)break;
				cnt=SAM::sz[p];
				l=lower_bound(q[i][j].begin(),q[i][j].end(),a)-q[i][j].begin();
				r=upper_bound(q[i][j].begin(),q[i][j].end(),b)-q[i][j].begin();
				Ans+=(ll)cnt*(r-l);
			}
		}
		printf("%lld\n",Ans);
	}
}

void solve2(){
	int i,l,r,a,b,p,len[MAXN]={0},pos[MAXN]={0},tmp;
	while(Q--){
		scanf("%s%d%d",w,&a,&b);
		Ans=0;
		p=SAM::rt;tmp=0;
		for(i=0;i<K;i++){
			SAM::match(p,w[i]-'a',tmp);
			pos[i]=p;len[i]=tmp;
		}
		for(i=a;i<=b;i++){
			if(R[i]-L[i]+1>len[R[i]])continue;
			p=SAM::jump(pos[R[i]],R[i]-L[i]+1);
			Ans+=SAM::sz[p];
		}
		printf("%lld\n",Ans);
	}
}

int main(){
	int i;
	scanf("%d%d%d%d%s",&N,&M,&Q,&K,s);
	for(i=0;i<M;i++)scanf("%d%d",&L[i],&R[i]);

	SAM::init();
	for(i=0;i<N;i++)SAM::ins(s[i]-'a');
	SAM::build();
	SAM::dfs(SAM::rt);
	
	if(K<Y)solve1();
	else solve2();
}